743B - Chloe and the sequence - CodeForces Solution


binary search bitmasks constructive algorithms implementation *1200

Please click on ads to support us..

Python Code:

import math

a, k = map(int, input().split())

if k % 2 != 0:
    print(1)
    exit()

if k & k-1 == 0:
    print(int(math.log2(k)) + 1)
    exit()

l = 2 ** math.floor(math.log2(k)) + 1
r = 2 ** math.ceil(math.log2(k)) - 1
center = (l + r) // 2

n = math.floor(math.log2(k))

while center != k:
    if center > k:
        r = center - 1
    else:
        l = center + 1
    
    center = (l + r) // 2
    n -= 1
    
print(n)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long int
#define ull unsigned long long int
#define nl "\n"
#define MOD 1e9+7
#define pb push_back
#define ppb pop_back
#define dbg(x) cerr<<#x<<"-"<<x<<nl;

/* solve function */
void solve(){
    ll n,k;
    cin>>n>>k;
    ll x = 2;
    int i=1;
    while(x<=pow(2,n)){
        if(k%x == x/2){
            cout<<i<<nl;
            return;
        }
        ++i;
        x *= 2;
    }
    cout<<-1<<nl;
}


/* main function */
int main(){
    clock_t start,end;
    start=clock();
    fast();
    ll t=1;
    ll i=1;
    /* cin>>t; */
    while(t--){
        /* cout<<"Case# "<<i<<": "; */
        solve();
        i++;
    }
    end=clock();
    double time=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<nl<<"Time: "<<time<<" sec"<<nl;
}


Comments

Submit
0 Comments
More Questions

834A - The Useless Toy
1407D - Discrete Centrifugal Jumps
1095B - Array Stabilization
291B - Command Line Arguments
1174B - Ehab Is an Odd Person
624B - Making a String
1064C - Oh Those Palindromes
1471A - Strange Partition
1746A - Maxmina
1746B - Rebellion
66C - Petya and File System
1746C - Permutation Operations
1199B - Water Lily
570B - Simple Game
599C - Day at the Beach
862A - Mahmoud and Ehab and the MEX
1525A - Potion-making
1744D - Divisibility by 2n
1744A - Number Replacement
1744C - Traffic Light
1744B - Even-Odd Increments
637B - Chat Order
546C - Soldier and Cards
18D - Seller Bob
842B - Gleb And Pizza
1746D - Paths on the Tree
1651E - Sum of Matchings
19A - World Football Cup
630P - Area of a Star
1030C - Vasya and Golden Ticket